#include "labirinto.h"

Labirinto::Labirinto() {
	temSolucao = false;
	sol_atual = new No();
	vector<int> m;
	m.push_back(1);
	m.push_back(6);
	m.push_back(8);
	mat.push_back(m);
	m.clear();

	m.push_back(2);
	m.push_back(6);
	m.push_back(7);
	mat.push_back(m);
	m.clear();

	m.push_back(3);
	m.push_back(7);
	m.push_back(1);
	mat.push_back(m);
	m.clear();

//	m.push_back(8);
//	m.push_back(7);
//	m.push_back(6);
//	mat.push_back(m);
//	m.clear();
//
//	m.push_back(7);
//	m.push_back(6);
//	m.push_back(5);
//	mat.push_back(m);
//	m.clear();
//
//	m.push_back(6);
//	m.push_back(2);
//	m.push_back(4);
//	mat.push_back(m);
//	m.clear();
}

Labirinto::~Labirinto() {
}

void Labirinto::escreve() {
	for (int i = 0; i < (int) mat.size(); i++) {
		for (int j = 0; j < (int) mat[i].size(); j++) {
			cout << mat[i][j] << ", ";
		}
		cout << endl;
	}
}

void Labirinto::solucao() {
	int posx = 0;
	int posy = 0;
	int custo = 0;
	pair<int, int> i = pair<int, int> (posx, posy);
	No *no = new No(i, custo, posx, posy);
	prioridade.push_back(no);

	while (!prioridade.empty()) {
		No *atual = prioridade.front();

		if (temSolucao && sol_atual->getCusto() <= atual->getCusto()) {
			prioridade.pop_front();
			continue;
		}

		pair<int, int> filho;
		filho.first = atual->getX() - 1;
		filho.second = atual->getY();

		if (filho.first >= 0 && !atual->naLista(filho)) {
			insereFilho(atual, filho);
		}

		filho.first = atual->getX() + 1;
		filho.second = atual->getY();

		if (filho.first < (int) mat.size() && !atual->naLista(filho)) {
			insereFilho(atual, filho);
		}

		filho.first = atual->getX();
		filho.second = atual->getY() - 1;

		if (filho.second >= 0 && !atual->naLista(filho)) {
			insereFilho(atual, filho);
		}

		filho.first = atual->getX();
		filho.second = atual->getY() + 1;

		if (filho.second < (int) mat.size() && !atual->naLista(filho)) {
			insereFilho(atual, filho);
		}

//		list<No*>::iterator it;
//		cout << "tamanho " << prioridade.size() << endl;
//		for (it = prioridade.begin(); it != prioridade.end(); it++) {
//			No* p = *it;
//			cout << " -> " << mat[p->getX()][p->getY()] << endl;
//			p->escreve(mat);
//		}
		prioridade.pop_front();
//		cout << "tamanho " << prioridade.size() << endl;
//		for (it = prioridade.begin(); it != prioridade.end(); it++) {
//			No* p = *it;
//			cout << " -> " << mat[p->getX()][p->getY()] << endl;
//			p->escreve();
//		}
//		cout << endl;
//		cout << endl;
//		break;
	}

	cout << "Caminho com menor Custo: ";
	sol_atual->escreve(mat);

}

void Labirinto::insereFilho(No* atual, pair<int, int> filho) {
	int at = mat[atual->getX()][atual->getY()];
	int fi = mat[filho.first][filho.second];

	int vAt = (at + atual->getCusto()) % 9;
	vAt = vAt == 0 ? 9 : vAt;

	int vF = (fi + atual->getCusto()) % 9;
	vF = vF == 0 ? 9 : vF;
	int c = atual->getCusto();
	if (vF <= vAt) {
		c = c + 1;
	} else {
		c = c + 10 - vF + 1;
	}

	if (temSolucao && c >= sol_atual->getCusto()) {
		return;
	}

	No *f = new No(*atual);
	f->add(filho, c, filho.first, filho.second);

	if (filho.first == (int) (mat.size() - 1) && filho.second == (int) (mat.size() - 1)) {
		temSolucao = true;
		sol_atual = f;
//		cout << "resp: ";
//		f->escreve(mat);
	} else {
		list<No*>::iterator it;
		for (it = prioridade.begin(); it != prioridade.end(); it++) {
			No* p = *it;
			if (c < p->getCusto()) {
				break;
			}
		}
		prioridade.insert(it, f);
	}
}
